A new class of sextic residue sequences of period prime p=4u2+27=6f+1 ≡ 3 ( mod 8) are presented. Their trace function representations are determined. And the exact value of the linear complexity is derived from the trace function representations. The result indicates that the new sextic sequences are quite good from the linear complexity viewpoint.

Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only O(M) time complexity for a sequence of length M.

In this letter, we examine the linear complexity of some 3-ary sequences, proposed by No, of period 3n-1(n=3ek, e, k integer) with the ideal autocorrelation property. The exact value of linear complexity k(6e)w is determined when the parameter r =. Furthermore, the upper bound of the linear complexity is given when the other forms of the value r is taken. Finally, a Maple program is designed to illustrate the validity of the results.

We focus on the relationship between the linearization method and linear complexity and show that the linearization method is another effective technique for calculating linear complexity. We analyze its effectiveness by comparing with the logic circuit method. We compare the relevant conditions and necessary computational cost with those of the Berlekamp-Massey algorithm and the Games-Chan algorithm. The significant property of a linearization method is that it needs no output sequence from a pseudo-random number generator (PRNG) because it calculates linear complexity using the algebraic expression of its algorithm. When a PRNG has n [bit] stages (registers or internal states), the necessary computational cost is smaller than O(2n). On the other hand, the Berlekamp-Massey algorithm needs O(N2) where N ( 2n) denotes period. Since existing methods calculate using the output sequence, an initial value of PRNG influences a resultant value of linear complexity. Therefore, a linear complexity is generally given as an estimate value. On the other hand, a linearization method calculates from an algorithm of PRNG, it can determine the lower bound of linear complexity.

In this letter we introduce new generalized cyclotomic sequences of order two and length pq firstly, then we determine the linear complexity and autocorrelation values of these sequences. Our results show that these sequences are rather good from the linear complexity viewpoint.

This paper contributes to a new generalized cyclotomic sequences of order two with respect to p1e1p2e2… ptet. The emphasis is on the linear complexity and autocorrelation of new prime-square sequences and two-prime sequences, two special cases of these generalized cyclotomic sequences. Our method is based on their characteristic polynomials. Results show that these sequences possess good linear complexity. Under certain conditions, the autocorrelation functions of new prime-square sequences and two-prime sequences may be three-valued.

In this paper we study relationships between the linear complexities of a sequence when treated as a sequence over two distinct fields. We obtain bounds for one linear complexity in the form of a constant multiple of the other, where the constant depends only on the fields, not on the particular sequence.

The linear complexity and its stability of periodic sequences are of fundamental importance as measure indexes on the security of stream ciphers and the k-error linear complexity reveals the stability of the linear complexity properly. The k-error linear complexity of periodic sequences is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. For 2pn-periodic binary sequences, where p is an odd prime and 2 is a primitive root modulo p2, we present and prove the unique expression of the linear complexity. Moreover we show a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.

In this letter we first introduce a new generalized cyclotomic sequence of order four with respect to pq, then we calculate the linear complexity and minimal polynomial of this sequence. Our results show that the new binary sequence is quite good from the linear complexity viewpoint.

We discuss a typical profile of the k-error linear complexity for balanced binary exponent periodic sequences and the number of periodic distinct sequences by their profiles. A numerical example with period 16 is also shown.

This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.

Recently six conjectures on linear complexities (LC) of some Kronecker sequences of two or three component sequences are proposed by Karkkainen. In, the LC of Kronecker sequences of two component sequences were studied by Uehara and Imamura, their results are true except in the case when eb 2 or when ea = eb = 1. In this paper the LC for Kronecker sequences of two component sequences are determined completely, and it is shown that all the six conjectures are true except in some special cases, which are listed and corrected.

In this paper, we will show that some families of periodic sequences over Z4 and Z8 with period multiple of 2r-1 generated by r-th degree basic primitive polynomials assorted by the root of each polynomial, and give the exact distribution of sequences for each family. We also point out such an instability as an extreme increase of their linear complexities for the periodic sequences by one-symbol substitution, i.e., from the minimum value to the maximum value, for all the substitutions except one.

Two classes of nonlinear feedforward logic (NLFFL) pseudonoise (PN) code generators based on the use of AND and majority logic (ML) gates are compared. Cross-correlation and code-division multiple-access (CDMA) properties of properly designed NLFFL sequences are found to be comparable with the properties of well-known linear PN codes. It is determined that code design employing ML gates with an odd number of inputs is easier compared with designing with AND gates. This is especially true when the degree of nonlinearity is large, since the nonbalance problem, e. g. , at the output of an AND gate, can be avoided. ML type sequences are less vulnerable to correlation attack and jamming by the m-sequence of an NLFFL generator

The maximum order complexity (MOC) of a sequence is a very natural generalization of the well-known linear complexity (LC) by allowing nonlinear feedback functions for the feedback shift register which generates a given sequence. It is expected that MOC is effective to reduce such an instability of LC as an extreme increase caused by the minimum changes of a periodic sequence, i. e. , one-symbol substitution, one-symbol insertion or one-symbol deletion per each period. In this paper we will give the bounds (lower and upper bounds) of MOC for the minimum changes of an m-sequence over GF(q) with period qn-1, which shows that MOC is much more natural than LC as a measure for the randomness of sequences in this case.

Two families of rapidly synchronizable spreading codes are compared using the same component codes. The influence of component code choice is also discussed. It is concluded that correlation, code-division multiple-access (CDMA) and information security (measured by the value of linear complexity) properties of Kronecker sequences are considerably better than those of Combination sequences. Combination sequences cannot be recommended for CDMA use unless the number of active users is few. CDMA performance of Kronecker sequences is almost comparable with that of linear pseudonoise (PN) code families of equal length when a Gold or Kasami code is used as the innermost code and the Barker code is used as the outermost code to guarantee satisfactory correlation and CDMA properties. Kronecker sequences possess a considerably higher value of linear complexity than those of the corresponding non-linear Geffe and majority logic type combination sequences. This implies they are highly non-linear codes due to the Kronecker product construction method. It is also observed that the Geffe type Boolean combiner resulted in better correlation and CDMA performance than with majority logic. The use of the purely linear exclusive-or combiner for considerable reduction of code synchronization time is not found recommendable although it results in good CDMA performance.

From a sequence {ai}i0 over GF(p) with period pn-1 we can obtain another periodic sequence {i}i0 with period pn-2 by deleting one symbol at the end of each period. We will give the bounds (upper bound and lower bound) of linear complexity of {i}i0 as a typical example of instability of linear complexity. Derivation of the bounds are performed by using the relation of characteristic polynomials between {ai}i0 and {ai(j)}i0={ai+j}i0, jGF(p){0}. For a binary m-sequence {ai}i0 with period 2n-1, n-1 a prime, we will give the explicit formula for the characteristic polynomial of {i}i0.

Firstly we show a usuful property of the fast algorithm for computing linear complexities of p-ary periodic sequences with period pn (p: a prime). Secondly the property is successfully applied to obtain the value distribution of the linear complexity for p-ary periodic sequences with period pn.

Recently two interesting conjectures on the linear complexity of binary complementary sequences of length 2nN0 were given by Karkkainen and Leppanen when those sequences are considered as periodic sequences with period 2nN0, where those sequences are constructed by successive concatenations or successive interleavings from a pair of kernel complementary sequences of length N0. Their conjectures were derived from numerical examples and suggest that those sequences have very large linear complexities. In this paper we give the exact formula of characteristic polynomials for those complementary sequences and show that their conjectures are true.

From a GF(q) sequence {ai}i0 with period qn - 1 we can obtain new periodic sequences {ai}i0 with period qn by inserting one symbol b GF(q) at the end of each period. Let b0 = Σqn-2 i=0 ai. It Is first shown that the linear complexity of {ai}i0, denoted as LC({ai}) satisfies LC({ai}) = qn if b -b0 and LC({ai}) qn - 1 if b = -b0 Most of known sequences are shown to satisfy the zero sum property, i.e., b0 = 0. For such sequences satisfying b0 = 0 it is shown that qn - LC({ai}) LC({ai}) qn - 1 if b = 0.